#include "encoder.h"

inline unsigned highest(byte_t byte)
{
    unsigned offset = sizeof(byte_t) * BITS_PER_BYTE - 1;
    return (byte >> offset) & 1;
}

inline unsigned int2char(unsigned u)
{
    return u | 0b110000;
}

void dfs(Node *u, string Encoding_list[], const string &encoded_str)
{
    if (!u)
        return;
    if (!u->lc && !u->rc) {
        Encoding_list[u->data] = encoded_str;
        return;
    }

    dfs(u->lc, Encoding_list, encoded_str + "0");
    dfs(u->rc, Encoding_list, encoded_str + "1");
}

void makeEncodingList(int *frequency, string Encoding_List[])
{
    Node *root = nullptr;
    pair<byte_t, int> select_list[ASCII_MAXSIZE] = {{0, 0}};
    Node *from_sl_to_bt[ASCII_MAXSIZE] = {nullptr};
    int select_size = 0;
    for (int i = 0; i < ASCII_MAXSIZE; i++)
        if (frequency[i]) {
            select_list[select_size++] = {i, frequency[i]};
        }

    if (select_size < 2) {
        Encoding_List[select_list[0].first] = '0';
        return;
    }

    while (select_size >= 2) {
        pair<byte_t, int> min_element1 = {'0', INF}, min_element2 = {'0', INF};
        int min_element1_pos = -1, min_element2_pos = -1;
        for (int i = 0; i < select_size; i++)
            if (select_list[i].second < min_element1.second) {
                min_element2_pos = min_element1_pos;
                min_element1_pos = i;
                min_element2 = min_element1;
                min_element1 = select_list[i];
            } else if (select_list[i].second == min_element1.second
                       || select_list[i].second < min_element2.second) {
                min_element2 = select_list[i];
                min_element2_pos = i;
            }

        Node *min1_node = (Node *) malloc(sizeof(Node));
        Node *min2_node = (Node *) malloc(sizeof(Node));
        Node *add_element = (Node *) malloc(sizeof(Node));

        if (!from_sl_to_bt[min_element1_pos]) {
            min1_node->data = min_element1.first;
            min1_node->val = min_element1.second;
            min1_node->lc = min1_node->rc = nullptr;
        } else {
            min1_node = from_sl_to_bt[min_element1_pos];
        }

        if (!from_sl_to_bt[min_element2_pos]) {
            min2_node->data = min_element2.first;
            min2_node->val = min_element2.second;
            min2_node->lc = nullptr;
            min2_node->rc = nullptr;
        } else {
            min2_node = from_sl_to_bt[min_element2_pos];
        }

        add_element->data = 0;
        add_element->val = min_element1.second + min_element2.second;
        add_element->lc = min1_node;
        add_element->rc = min2_node;

        int skip_count = 0;
        for (int i = 0; i < select_size; i++) {
            if (i == min_element1_pos || i == min_element2_pos)
                skip_count++;
            else {
                select_list[i - skip_count] = select_list[i];
                from_sl_to_bt[i - skip_count] = from_sl_to_bt[i];
            }
        }

        select_list[select_size - 2] = {add_element->data, add_element->val};
        from_sl_to_bt[select_size - 2] = add_element;
        select_size--;
        root = add_element;
    }
    dfs(root, Encoding_List, "");
}

void Encoding(const byte_t *buffer, size_t read_count, string *EncodingList, FILE *out)
{
    for (int i = 0; i < ASCII_MAXSIZE; i++) {
        byte_t length = 0;
        short encode = 0;
        length = EncodingList[i].size();
        for (auto e: EncodingList[i])
            encode = (short) (encode * 2 + e - '0');
        virtualFwrite(&length, sizeof length, 1, out);
        virtualFwrite(&encode, sizeof encode, 1, out);
    }

    for (int i = 0; i < read_count; i++) {
        for (auto e: EncodingList[buffer[i]]) {
            virtualFwrite(&e, sizeof(byte_t), 1, out);
        }
    }
}


byte_t writeByte(FILE *fp, byte_t byte)
{
    byte_t bits[BITS_PER_BYTE] = {0};

    for (byte_t &bit: bits) {
        bit = int2char(highest(byte));
        byte <<= 1;
    }

    return fwrite(bits, sizeof(byte_t), BITS_PER_BYTE, fp);
}

size_t virtualFwrite(void *buff, size_t elementSize, size_t count, FILE *fp)
{
    auto pbyte = (byte_t *) buff;
    size_t byteCount = 0;

    for (size_t i = 0; i < count; ++i) {
        for (size_t j = 0; j < elementSize; ++j) {
            writeByte(fp, *pbyte++);
            ++byteCount;
        }
    }

    return byteCount;
}